package main

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
	p := list1
	q := list2
	head := &ListNode{}
	needle := head
	for q != nil && p != nil {
		var v int
		if p.Val > q.Val {
			v = q.Val
			q = q.Next
		} else {
			v = p.Val
			p = p.Next
		}
		needle.Next = &ListNode{Val: v}
		needle = needle.Next
	}

	if q != nil {
		needle.Next = q
	} else if p != nil {
		needle.Next = p
	}
	return head.Next
}
